package LeetCode;

import java.util.*;

public class LC_675_CutOffTreesforGolfEvent {

    public static void main(String[] args) {

    }

    class Solution {
        class Tree {
            int row;
            int col;
            int height;

            Tree(int r, int c, int h) {
                this.row = r;
                this.col = c;
                this.height = h;
            }
        }

        private final int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        private int bfs(List<List<Integer>> forest, Tree start, Tree end, int m, int n) {
            Queue<Tree> q = new LinkedList<>();
            boolean[][] visit = new boolean[m][n];
            q.offer(start);
            visit[start.row][start.col] = true;
            int level = 0;
            while (!q.isEmpty()) {
                int curSize = q.size();
                for (int i = 0; i < curSize; i++) {
                    Tree cur = q.poll();
                    if (cur.row == end.row && cur.col == end.col) return level;
                    for (int[] d : dir) {
                        int x = cur.row + d[0];
                        int y = cur.col + d[1];
                        if (x < 0 || x >= m || y < 0 || y >= n || visit[x][y] || forest.get(x).get(y) == 0) continue;
                        q.offer(new Tree(x, y, -1));
                        visit[x][y] = true;
                    }
                }
                level++;
            }
            return -1;
        }

        public int cutOffTree(List<List<Integer>> forest) {
            int m = forest.size();
            int n = forest.get(0).size();
            List<Tree> trees = new ArrayList<>();
            trees.add(new Tree(0, 0, Integer.MIN_VALUE + 2));
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int h = forest.get(i).get(j);
                    if (h > 0) {
                        trees.add(new Tree(i, j, h));
                    }
                }
            }
            trees.sort(Comparator.comparingInt(a -> a.height));
            int res = 0;
            for (int i = 0; i < trees.size() - 1; i++) {
                int step = bfs(forest, trees.get(i), trees.get(i + 1), m, n);
                if (step == -1) return -1;
                res += step;
            }
            return res;
        }
    }
}